\documentclass[utf8]{ctexart}

\usepackage[a4paper,left=1.25in,right=1.25in,top=1in,bottom=1in]{geometry}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{booktabs}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{float}
\usepackage{indentfirst}
\usepackage{gnuplot-lua-tikz}
\usepackage{tikz}
\usetikzlibrary{shapes,arrows}
\usetikzlibrary{shapes.geometric, arrows}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{newclude}
\usepackage[perpage]{footmisc}

\raggedbottom	% 令页面在垂直方向向顶部对齐
\renewcommand\qedsymbol{QED}
\newcommand{\sign}[1]{\mathrm{sgn}(#1)}
\everymath{\displaystyle}   % 行内公式采用行间公式格式排列

\title{第一次理论作业}
\author{姓名：殷文良\qquad 学号：3200101893}
\date{}

\begin{document}
\maketitle
\CTEXsetup[format={\Large\bfseries}]{section}

\begin{enumerate}
\item
  % 问题1
  \textbf{解}\par
  （1）设二分法的初始区间长度为$\Delta_0$，则$\Delta_0 = 3.5-1.5=2$。\\
  显然，第$n$次二分后区间长度为
  \begin{equation*}
    \Delta_n =\frac{\Delta_0}{2^n}=\frac{1}{2^{n-1}}
  \end{equation*}
  （2）设第$b$次二分后区间中点为$x_n$，则
  \begin{equation*}
    \vert x_n - r \vert \le \frac{\Delta_n}{2} = \frac{1}{2^n}
    \end{equation*}
\item
  % 问题2
  \begin{proof}
    设$f(x)$的根为$x^*$，则由上题论述可得，在第$n$次二分后$x_n$的绝对误差为
    \begin{equation*}
      e(x_n) = \vert x^* - x_n \vert \le \frac{b_k-a_k}{2} = \frac{b_0-a_0}{2^{n+1}}
    \end{equation*}
    故$x_n$的相对误差为
    \begin{equation*}
      e_r(x_n) = \frac{e(x_n)}{x^*} \le \frac{e(x_n)}{a_0} = \frac{b_0-a_0}{2^{n+1}\cdot a_0}
    \end{equation*}
    $\forall \epsilon >0$，为保证$e_r(x_n)\le \epsilon$，只需令
    \begin{equation*}
      \frac{b_0-a_0}{2^{n+1}\cdot a_0} \le \epsilon
    \end{equation*}
    整理得
    \begin{equation*}
      n\ge \frac{\log{(b_0-a_0)}-\log{\epsilon}-\log{a_0}}{\log{2}}-1.
    \end{equation*}
  \end{proof}
\item
  % 问题3
  \textbf{解}\par
  由于$p(x)=4x^3-2x^2+3$，所以$p'(x)=12x^2-4x$。所以牛顿迭代法的迭代公式为
  \begin{align*}
    x_{n+1} &= x_n - \frac{f(x_n)}{f'(x_n)}\\
    &= x_n - \frac{4x_n^3-2x_n^2+3}{12x_n^2-4x_n}\\
    &= \frac{8x_n^3-2x_n^2-3}{12x_n^3-4x_n}
  \end{align*}
  牛顿迭代法的前4次迭代结果如表\ref{table1}。
  \begin{table}[H]
    \centering
    \begin{tabular}{cc}
      \toprule
      $n$ & $x_n$ \\
      \midrule
      0 & -1 \\
      1 &  1.6250\\
      2 &  0.5789\\
      3 &  -170.1680\\
      4 &  0.6677\\
      \bottomrule
    \end{tabular}
    \caption{牛顿迭代法的前4次迭代结果}
    \label{table1}
  \end{table}
\item
  % 问题4
  \textbf{解}\par
  设$f(x)$的零点为$\alpha$。由于$x_{n+1}=x_n - \frac{f(x_n)}{f'(x_0)}$，故
  \begin{align*}
    e_{n+1} &= x_{n+1} - \alpha\\
    &= x_n -\frac{f(x_n)}{f'(x_0)} - \alpha\\
    &= e_n - \frac{f(x_n)}{f'(x_0)}\\
    &= \cdots\\
    &= e_0 - \frac{f(x_0)+f(x_1)+\cdots+f(x_n)}{f'(x_0)}
  \end{align*}
  根据题意，$e_{n+1}=Ce_n^s$，其中$s$为常数。\par
  若$s\ne 1$，则
  \begin{align*}
    e_{n+1} &= Ce_n^s\\
    &= C\cdot C^{s}\cdot e_{n-1}^{s^2}\\
    &= \cdots\\
    &= C\cdot C^s\cdot \cdots C^{s^n}\cdot e_0^{s^{n+1}}                                      
  \end{align*}
  与上式矛盾，故$s=1$，从而$e_{n+1}=C^{n+1}e_0$。\par
  联立上述两式可得
  \begin{equation*}
    1-C^{n+1} = \frac{\sum_{i=0}^{i=n}{f(x_i)}}{f'(x_0)e_0}
  \end{equation*}
  整理得
  \begin{equation*}
    C = \sqrt[n+1]{1-\frac{\sum_{i=0}^{i=n}{f(x_i)}}{f'(x_0)(x_0-\alpha)}}.
  \end{equation*}
\item
  % 问题5
  \textbf{解}\par
  令$f(x)=\arctan{x}$，下面分两种情况讨论其收敛性。\par
  （1）$x_0 =0$。此时$x_n=0(n=1,2,\cdots)$，显然迭代序列收敛于0。\par
  （2）$x_0\ne 0$。不失一般性，不妨设$x_0\in (0,\frac{\pi}{2})$，$x_0\in (-\frac{\pi}{2},0)$的情况同理可证。由于$\frac{f(x)}{x}<1(x>0)$，从而$x_{n+1}<x_n$恒成立，即$x_0>x_1>\cdots$，$\{x_n\}$是单调递减的序列。又$x_n>0$，所以由单调有界定理，迭代序列$\{x_n\}$收敛于0。\par
  综上，迭代序列$\{x_n\}(n=0,1,\cdots)$收敛且收敛于0。
\item
  % 问题6
  \textbf{解}\par
  构造迭代序列$x_{n+1}=\frac{1}{x_n+p}$，其中$x_0=0,n=1,2,\cdots$。令$g(x)=\frac{1}{x+p}$，设$x^*$为$g(x)$的一个不动点，即
  \begin{equation*}
     x^*=\frac{1}{x^*+p},\quad p>1
  \end{equation*}
  解得$x^*=\frac{-p+\sqrt{p^2+4}}{2}$。\par
  下面证明迭代序列$x_{n+1}=\frac{1}{x_n+p}$确实收敛于$x^*$。
  \begin{proof}
  （1）由于$p>1$，所以
  \begin{equation*}
    x^* = \frac{-p+\sqrt{p^2+4}}{2} = \frac{2}{\sqrt{p^2+4}+p} < \frac{2}{\sqrt{5}+1} < 1
  \end{equation*}
  因此$x=g(x)$在区间(0,1)上有实根$x^*$。\par
  （2）$g'(x)=-\frac{1}{(x+p)^2}$在$(0,1)$内连续，且
  \begin{equation*}
    \vert g'(x^*)\vert = \frac{1}{(x+p)^2} < \frac{1}{p^2} < 1
  \end{equation*}
  根据（1）和（2），由迭代法收敛的充分条件可知，该迭代序列必然收敛。
  \end{proof}
\item
  % 问题7
  \textbf{解}\par
  若$a_0<0<b_0$，则不能再用相对误差作为一个判断标准，此时改用绝对误差$e(x_n)$，即对于给定的$\epsilon>0$，要求
  \begin{equation*}
    e(x_n) \le \epsilon
  \end{equation*}
  类似于问题2的证明，容易得到
  \begin{equation*}
    n \ge \frac{\log{(b_0-a_0)}-\log{\epsilon}}{\log{2}}-1
  \end{equation*}
  \end{enumerate}

\end{document}
